﻿#include<stdio.h>
//1、某种特殊的数列 a1, a2, a3, ... 的定义如下：$a_1 = 1, a_2 = 2, ..., a_n = 2 * a{ n−1 }~+ a{ n - 2 } $其中(n >
//	2)。给出任意一个正整数k，求该数列的第k项模以32767的结果是多少？
//	输入描述：
//	第1行是测试数据的组数 n ，后面跟着 n 行输入。
//	每组测试数据占1行，包括一个正整数 k(1 ≤ k < 1000000) 。
//	输出描述： n 行，每行输出对应一个输入。输出应是一个非负整数。
int main()
{
	long n;
	long arr[100000] = { 1, 2 };
	//先生成数列，注意这里存入的是取模后的结果，否则数据会越界
	for (int i = 2; i < 100000; i++)
	{ 
		arr[i] = (arr[i - 1] * 2 + arr[i - 2]) % 32767; 
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int num;
		scanf("%d", &num);
		printf("%ld\n", arr[num - 1]);
	}
	return 0;
}
